#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <inttypes.h> 
#include <stdbool.h>
#include <errno.h>
#include <time.h>
#include <set>
#include <algorithm>
#include <fcntl.h>
#include "../../ursax.h"
#include "cache-entry.h"

using namespace std;

// the highest bit of the pos member of struct Segment is used as a flag for write back
const uint64_t WRITING_BACK = 1UL << 63;
const uint64_t WRITING_BACK_MASK = ~WRITING_BACK;

// 相当于定义 == 运算符为lhs和rhs有交集
static inline bool operator < (const Segment& lhs, const Segment& rhs)
{
	return lhs.end <= rhs.begin;
}

#define INVALID_FUNCTION ((cb_journal_free_t)-1UL)
struct CacheRegistry : public set<Segment>
{
	set<Segment> cache_file_pos;
	cb_journal_free_t free_journal_cb;
	void* data;

	CacheRegistry(cb_journal_free_t fun, void* data)
	{
		this->free_journal_cb = fun;
		this->data = data;
	}
	CacheRegistry()
	{
		this->free_journal_cb = NULL;
		this->data = NULL;
	}
};

typedef CacheRegistry::iterator Iterator;
typedef set<Segment>::iterator SIterator;

template<bool> struct StaticAssert;
template<> struct StaticAssert<true> {};


// create a new CacheRegistry
struct CacheRegistry* cache_create(cb_journal_free_t free_fun, void* data)
{
	return new CacheRegistry(free_fun, data);
}

// destroy a cache registry
void cache_destroy(struct CacheRegistry* cr)
{
	if(!cr){
		return;
	}
	delete cr;
}

static inline void insert_cache_file_pos_record(struct CacheRegistry* cr, struct Segment* s /*segment for offset*/)
{
	if(!cr->free_journal_cb){
		return;
	}

	s->logic_pos &= WRITING_BACK_MASK;

	struct Segment ls;
	ls.begin_pos = s->logic_pos;
	ls.end_pos = s->logic_pos + s->end - s->begin;
	ls.reference = 1;
	LOG_DEBUG("insert_cache_file_pos_record (%016lx %016lx %016lx)", ls.begin_pos, ls.end_pos, ls.reference);
	cr->cache_file_pos.insert(ls);
}

static inline void adjust_cache_file_pos_recode_reference(struct CacheRegistry* cr, struct Segment s, int inc)
{
	if(!cr->free_journal_cb){
		return;
	}

	s.logic_pos &= WRITING_BACK_MASK;

	struct Segment ls;
	ls.begin_pos = s.logic_pos;
	ls.end_pos = s.logic_pos + s.end - s.begin;
	LOG_DEBUG("adjust_cache_file_pos_recode_reference (%lx, %lx) (%lx, %lx) inc %d", s.begin, s.end, ls.begin_pos, ls.end_pos, inc);
	pair<SIterator,SIterator> range = cr->cache_file_pos.equal_range(ls);
	if(range.first == range.second){
		return;
	}

	struct Segment* _it = const_cast<struct Segment*>(&*range.first);
	_it->reference += inc;
	if(range.first->reference == 0){
		if(cr->free_journal_cb && cr->free_journal_cb != INVALID_FUNCTION){
			cr->free_journal_cb(range.first->begin_pos, range.first->end_pos, cr->data);
		}
		LOG_DEBUG("adjust_cache_file_pos_recode_reference erase (%016lx %016lx %016lx)", range.first->begin_pos, range.first->end_pos, range.first->reference);
		cr->cache_file_pos.erase(range.first);
	}
}

static inline int _cache_print(struct CacheRegistry* cr)
{
	for(Iterator it = cr->begin(); it != cr->end(); it++){
		LOG_INFO("(%016lx %016lx %016lx) ", it->begin, it->end, it->logic_pos);
	}
	LOG_INFO("CacheRegistry cache1 print end");
	if(cr->free_journal_cb){
		for(SIterator it = cr->cache_file_pos.begin(); it != cr->cache_file_pos.end(); it++){
			LOG_INFO("(%016lx %016lx %016lx) ",  it->begin, it->end, it->logic_pos);
		}
	}
	LOG_INFO("CacheRegistry cache2 print end");
	return 0;
}

int print_cache(struct CacheRegistry* cr)
{
	return _cache_print(cr);
}

static inline void cache_print(struct CacheRegistry* cr)
{
#ifdef TEST_CACHE_ENTRY
	LOG_DEBUG("CacheRegistry cache1 print end", _cache_print(cr));
#endif
}

static inline void check_cache_registry_error(struct CacheRegistry* cr)
{
	if(cr->size() == 0){
		if(cr->free_journal_cb){
			if(cr->cache_file_pos.size() == 0){
				LOG_INFO("ATTENTION: cr->cache_file_pos.size() == 0 !!!!");
			}else{
				LOG_ERROR("fix-me: cache-entry bug, CacheRegistry is 0, cache_file_pos not 0 !!!!");
			}
		}
	}
}

static inline Iterator erase(struct CacheRegistry* cr, Iterator it)
{
	LOG_DEBUG("erase Segment begin %016lx end %016lx pos %016lx", it->begin, it->end, it->logic_pos);
	Iterator next = it;
	++next;
	adjust_cache_file_pos_recode_reference(cr, *it, -1);
	cr->erase(it);
	check_cache_registry_error(cr);
	return next;
}

static inline void process_overlap(struct CacheRegistry* cr, Iterator it, struct Segment* s)
{
	// it's safe to "shrink" segments
	struct Segment* _it = const_cast<struct Segment*>(&*it);
	
	if (s->begin <= it->begin)
	{
		if (s->end >= it->end)
		{
			// cr->erase(it);
			erase(cr, it);
		}
		else
		{
			_it->logic_pos += s->end - it->begin;	// op add will preserve WRITING_BACK flag
			_it->begin = s->end;
		}
	}
	else
	{
		if (s->end >= it->end)
		{
			_it->end = s->begin;
		}
		else
		{
			struct Segment ns;
			ns.end = it->end;
			_it->end = s->begin;
			ns.begin = s->end;
			ns.logic_pos = _it->logic_pos + (s->end - _it->begin);	// op add will preserve WRITING_BACK flag
			adjust_cache_file_pos_recode_reference(cr, ns, 1);
			cr->insert(it, ns);
		}
	}
}

// insert a segment s, into the cache registry
// return 0 for success, <0 for failure
int cache_insert(struct CacheRegistry* cr, struct Segment* /*IN*/ s)
{
	LOG_DEBUG("insert a Segment begin %lu end %lu pos %lu", s->begin, s->end, s->logic_pos);
	if(s->begin >= s->end){
		LOG_FATAL("s begin %lu s end %lu, s pos", s->begin, s->end, s->logic_pos);
		return -1;
	}
	pair<Iterator,Iterator> range = cr->equal_range(*s);
	// no one same as *s
	if (range.first == range.second)
	{
		insert_cache_file_pos_record(cr, s);
		cr->insert(range.first, *s);
		cache_print(cr);
		return 0;
	}

	// some one same as *s
	Iterator hint = range.second; --range.second;
	if(range.first != range.second){
		Iterator it = range.first; ++it;
		while(it != range.second)
		{
			it = erase(cr, it);
		}
	}

	process_overlap(cr, range.first, s);
	if (range.second != range.first)
	{
		process_overlap(cr, range.second, s);
	}

	insert_cache_file_pos_record(cr, s);
	cr->insert(hint, *s);
	cache_print(cr);
	return 0;
}

// look up in the cache registry for a segment [s->begin, s->end),
// return 0 for success, <0 for failure
// s->pos and s->end will be set to proper value when succeeded
int cache_lookup(struct CacheRegistry* cr, struct Segment* /*IN*/ s, struct Segment* so, void** iterator)
{
	Iterator it;
	StaticAssert<sizeof(it) == sizeof(*iterator)>();

	if (*iterator == NULL)
	{
		it = cr->lower_bound(*s);
	}
	else
	{
		memcpy(&it, iterator, sizeof(it));
		++it;
	}

	if (it == cr->end() || *s < *it)
	{
		*iterator = NULL;
		return -1;
	}

	so->begin = it->begin;
	so->end = min(s->end, it->end);
	so->logic_pos = it->logic_pos & WRITING_BACK_MASK;	// remove WRITING_BACK flag, if there is
	memcpy(iterator, &it, sizeof(it));
	return 0;
}

int cache_count_segment(struct CacheRegistry* cr, struct Segment is)
{
	int count = 0;
	int ret = 0;
	void *it = NULL;
	struct Segment os;
	while((ret = cache_lookup(cr, &is, &os, &it)) == 0){
		count++;
	}
	return count;
}

int cache_lookup_multy(struct CacheRegistry* cr, struct Segment* /*IN*/ is, struct Segment* /*OUT*/ *os)
{
	pair<Iterator,Iterator> range = cr->equal_range(*is);
	if (range.first == range.second)
	{
		return -1;
	}
	int count = cache_count_segment(cr, *is);
	struct Segment* ss = *os = (struct Segment*)malloc(sizeof(*is)*count);
	int i = 0;
	for(Iterator it = range.first; it != range.second;){
		memcpy(&ss[i++], &(*it++), sizeof(ss[0]));
		ss[i-1].logic_pos &= WRITING_BACK_MASK;
	}
	return count;
}

// actually this function will get the real logic position
int cache_lookup_journal(struct CacheRegistry* cr, struct Segment* /*IN-OUT*/ s, uint64_t cache_size)
{
	pair<Iterator,Iterator> range = cr->equal_range(*s);
	if (range.first == range.second)
	{
		return -1;
	}

	for(Iterator it = range.first; it != range.second; it++){
		struct Segment pos_seg;
		uint64_t logic_pos= it->logic_pos & WRITING_BACK_MASK;
		pos_seg.begin_pos = logic_pos;
		pos_seg.end_pos = logic_pos + it->end - it->begin;
		pair<Iterator,Iterator> pos_range = cr->cache_file_pos.equal_range(pos_seg);
		if(pos_range.first == pos_range.second){
			return -1;
		}
		if((pos_range.first->begin_pos - s->logic_pos) % cache_size == 0){
			LOG_DEBUG("cache_lookup_journal one  %016lx %016lx %016lx", pos_range.first->begin_pos, pos_range.first->end_pos, s->logic_pos);
			memcpy(s, &(*pos_range.first), sizeof(*s));
			return 0;
		}
	}
	return -1;
}

int cache_remove(struct CacheRegistry* cr, struct Segment* is)
{
	LOG_DEBUG("offset %ld len %d", is->begin, is->end);
	pair<Iterator,Iterator> range = cr->equal_range(*is);
	if (range.first == range.second)
	{
		return -1;
	}
	erase(cr, range.first);
	return 0;
}

int cache_clear_range(struct CacheRegistry* cr, uint64_t offset, uint32_t len)
{
	LOG_DEBUG("offset %ld len %d", offset, len);
	struct Segment s;
	s.begin = offset;
	s.end = offset + len;
	s.logic_pos = 0;
	cache_insert(cr, &s);
	return cache_remove(cr, &s);
}

uint64_t cache_count_coverage(struct CacheRegistry* cr)
{
	uint64_t count = 0;
	for(Iterator it = cr->begin(); it != cr->end(); it++){
		count += it->end - it->begin;
	}
	return count;
}

// get the a segment of the cache registry for writing back
// return number of segments remained in the registry (>=0) for success, <0 for failure
int begin_write_back(struct CacheRegistry* cr, struct Segment* /*OUT*/ s)
{
	int size = (int)cr->size();
	if (unlikely(size == 0))
	{
		return -1;
	}

	Iterator it = cr->begin();
	*s = *it;
	s->logic_pos &= WRITING_BACK_MASK;	// remove WRITING_BACK flag, if there is
	const_cast<struct Segment*>(&*it)->logic_pos |= WRITING_BACK;		// add WRITING_BACK flag
	return size;
}

void debug_test_set_all_write_back(struct CacheRegistry* cr)
{
	LOG_WARN("attention: debug_test_set_all_write_back is debug funtion now running !!!");
	for(Iterator it = cr->begin(); it != cr->end(); it++){
		const_cast<struct Segment*>(&*it)->logic_pos |= WRITING_BACK;
	}
}

// complete the write back operation, by removing the segment (returned by begin_write_back) from the cache
// return number of segments remained in the registry (>=0) for success, <0 for failure
int end_write_back(struct CacheRegistry* cr, struct Segment* /*IN*/ s)
{
	pair<Iterator, Iterator> range = cr->equal_range(*s);
	Iterator it = range.first;
	while(it != range.second)
	{
		if (it->logic_pos | WRITING_BACK)
		{
			it = erase(cr, it);
		}
		else
		{
			++it;
		}
	}
	return (int)cr->size();
}

void clear_all_iterm(struct CacheRegistry* cr)
{
	struct Segment s;

	cb_journal_free_t old_cb = cr->free_journal_cb;
	cr->free_journal_cb = INVALID_FUNCTION;

	while(true){
		int ret = begin_write_back(cr, &s);
		if(ret < 0){
			break;
		}
		end_write_back(cr, &s);
	}
	cr->free_journal_cb = old_cb;
}
